package com.gorkr.labuladong.data_struct.array;

/**
 * @author gorkr
 * @date 2022/06/03 17:28
 **/
public class M304RangeSumQuery2DImmutable {

    private int[][] preSum;

    public M304RangeSumQuery2DImmutable(int[][] matrix) {
        preSum = new int[matrix.length+1][matrix[0].length+1];
        for (int i = 1; i < preSum.length; i++) {
            for (int j = 1; j < preSum[0].length; j++) {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }


    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2+1][col2+1] - preSum[row1][col2+1] - preSum[row2+1][col1]+ preSum[row1][col1];
    }

}
    